package com.czk.stack;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中缀表达式转为字符串集合
 * 中缀表达式转换为后缀表达式
 * 后缀表达式计算的实现
 * @Author:ChenZhangKun
 * @Date: 2020/6/21 13:16
 */
public class PolandNotation {
    public static void main(String[] args) {
        // 先定义逆波兰表达式
        // （3+4）*5-6 对应的逆波兰表达式为3 4 + 5 * 6 -
        // 数字和符号之间使用空格隔开
        String suffixExpression="4 4 + 5 * 6 -";
        System.out.println(getResult(getListString(suffixExpression)));

        System.out.println(toInfixExpression("(3+4)*5-6*6"));

        System.out.println(infixToSuffixExpression(toInfixExpression("(3+4)*5-6*6")));

        System.out.println(getResult(infixToSuffixExpression(toInfixExpression("(3+4)*5-6*6"))));
    }

    /**
     * 将字符串放入集合中
     * @param suffixExpression
     * @return
     */
    private static List<String> getListString(String suffixExpression){
        // 将字符串分割
        String[] s = suffixExpression.split(" ");
        List<String> list=new ArrayList<>(10);
        for (int i = 0; i < s.length; i++) {
            list.add(s[i]);
        }
        return list;
    }

    /**
     * 后缀表达式计算结果
     * @param list
     * @return
     */
    private static int getResult(List<String> list){
        // 创建栈
        Stack<String> stack=new Stack<>();
        // 遍历list
        for (String s : list) {
            // 使用正则表达式来取出数字
            if (s.matches("\\d+")){
                // 入栈
                stack.push(s);
            }else {
                // 弹出两个数运算后再入栈
                int num2 =Integer.parseInt( stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res=0;
                // 判断该符号是什么
                if (s.equals("+")){
                    res= num1+num2;
                }else if (s.equals("-")){
                    res=num1-num2;
                }else if (s.equals("*")){
                    res=num1*num2;
                }else {
                    res=num1/num2;
                }
                // 计算结果从新压入栈中
                stack.push(res+"");
            }
        }
        // 得到计算的结果
        return Integer.parseInt(stack.pop());
    }

    /**
     * 将中缀表达式字符串加入集合中，得到集合的中缀表达式
     * @param inFixExpression 传入种植表达式
     * @return
     */
    // 将表达式转为list集合存储
    public static List<String> toInfixExpression(String inFixExpression){
        List<String> list=new ArrayList<>(15);
        // 指针，用于遍历
        int index=0;
        // 对多位数的拼接工作
        String s;
        // 遍历到的字符是否是符号
        char ch=' ';
        do {
            if ((ch=inFixExpression.charAt(index))>57||(ch=inFixExpression.charAt(index))<48){
                // 非数字
                list.add(""+ch);
                index++;
            }else {
                s="";
                // 判断数字到那一位结束
                while (index<inFixExpression.length()&&(ch=inFixExpression.charAt(index))>=48&&(ch=inFixExpression.charAt(index))<=57){
                    s+=ch;
                    index++;
                }
                // 将数字加入集合中
                list.add(s);
            }
        }while (index<inFixExpression.length());
        return list;
    }

    /**
     * 中缀表达式的集合转换为后缀表达式
     * @param list 中缀表达式的list集合
     * @return
     */
    public static List<String> infixToSuffixExpression(List<String> list){
        // 定义符号栈
        Stack<String> s1=new Stack<>();
        // 定义数字栈 因为数字栈没有弹栈操作，可以用list代替
        //Stack<String> s2=new Stack<>();
        List<String> numList=new ArrayList<>(15);
        // 遍历集合
        for (String s : list) {
            // 是数字的情况
            if (s.matches("\\d+")){
                numList.add(s);
            }else if (s.equals("(")){
                // 左括号进入符号栈
                s1.push(s);
            }else if (s.equals(")")){
                // 右括号的的情况
                // 将符号栈中的左括号前的符号加入数字栈
                while (!s1.peek().equals("(")){
                    numList.add(s1.pop());
                }
                // 将小括号弹出站顶
                s1.pop();
            }else {
                // 优先级的问题
                // s1为空时或栈顶为左括号时，直接加入符号栈
                if (s1.isEmpty()||s1.peek().equals("(")){
                    s1.push(s);
                }else  {
                    // s1栈顶的运算符的优先级比当前运算符的优先级大的时候
                    while (s1.size() != 0 && Operation.getPriority(s1.peek()) >= Operation.getPriority(s)) {
                        // 将栈顶元素压如数字栈中
                        numList.add(s1.pop());
                    }
                    // 优先级大于栈顶操作符的优先级时当前操作符压入栈顶
                    s1.push(s);
                }
            }
        }
        // 将s1中的符号加入数字栈中
        while (true){
            if (s1.size()!=0){
                numList.add(s1.pop());
            }else {
                break;
            }
        }
        return numList;
    }

}

/**
 * 获取运算符的优先级
 */
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;
    // 返回优先级
    public static int getPriority(String operation){
        int result=0;
        switch (operation){
            case "+":
                result=ADD;
                break;
            case "-":
                result= SUB;
                break;
            case "*":
                result=MUL;
                break;
            case "/":
                result=DIV;
                break;
        }
        return result;
    }
}
